/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/palindromic-partitioning-ii
   @Language: C++
   @Datetime: 19-03-25 15:57
   */

class Solution {
public:
	/**
	 * @param s: A string
	 * @return: An integer
	 */
	int minCut(string &s) {
		// write your code here
		if(s.length()<1) return 0;
		int n=s.length();
		vector<vector<bool> > dp(n,vector<bool>(n,false));
		vector<int> cut(n+1);
		for(int i=0; i<n; ++i)
			cut[i]=n-i;
		for(int i=n; i--;){
			for(int j=i; j<n; ++j){
				if (s[i]==s[j] && (j-i<2 || dp[i+1][j-1])){
					dp[i][j]=true;
					cut[i]=min(cut[i],cut[j+1]+1);
				}
			}
		}
		return cut[0]-1;
	}
};
